class Solution {
public:
    int numSquares(int n) {
        vector<vector<int>> dp(sqrt(n)+1,vector<int>(n+1));
        //初始化第一行和第一列为无穷大
        for(int j = 0;j<=n;j++)
        {
            dp[0][j] = 0x7f7f7f7f7f;
        }//将第一行初始化为最大值
        dp[0][0] = 0;
        //然后填写这个dp表
        for(int i = 1;i<=sqrt(n);i++)
        {
            for(int j = 0;j<=n;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j>=i*i)
                {
                    dp[i][j] = min(dp[i][j],dp[i][j-i*i]+1);
                }
            }
        }
        return dp[sqrt(n)][n];
    }
};//第一种写法，没有使用记忆化数组进行优化
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        //初始化第一行和第一列为无穷大
        for(int j = 0;j<=n;j++)
        {
            dp[j] = 0x7f7f7f7f7f;
        }//将第一行初始化为最大值
        dp[0] = 0;
        //然后填写这个dp表
        for(int i = 1;i<=sqrt(n);i++)
        {
            for(int j = i*i;j<=n;j++)
            {
                if(j>=i*i)
                {
                    dp[j] = min(dp[j],dp[j-i*i]+1);
                }
            }
        }
        return dp[n];
    }
};//第二种写法使用记忆化数组进行优化